package Array;//编写一个高效的算法来判断 m x n 矩阵中，是否存在一个目标值。该矩阵具有如下特性：
//
// 
// 每行中的整数从左到右按升序排列。 
// 每行的第一个整数大于前一行的最后一个整数。 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
//输出：true
// 
//
// 示例 2： 
//
// 
//输入：matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
//输出：false
// 
//
// 
//
// 提示： 
//
// 
// m == matrix.length 
// n == matrix[i].length 
// 1 <= m, n <= 100 
// -10⁴ <= matrix[i][j], target <= 10⁴ 
// 
// Related Topics 数组 二分查找 矩阵 👍 612 👎 0


//leetcode submit region begin(Prohibit modification and deletion)
class searchMatrix {
    public boolean searchMatrix(int[][] matrix, int target) {
        int m = matrix[0].length;
        for(int i=0;i<matrix.length;){
            //比较每一行的最后一个
            int num = matrix[i][m-1];
            //看每一行最后一个是不是大于target，如果大于target,就在本行找,本行找不到，就是false
            if(num > target){
                for(int j=0;j<m;j++){
                    if(matrix[i][j]==target){
                        return true;
                    }
                }
                return false;
            }else if(num<target){
                i++;   //进入下一行
            }else{
                return true;
            }
        }
        return false;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
